# 01背包问题(标准版) (0/1 Knapsack Problem)
# Date: 2025/3/24

"""
题目:
有n件物品和一个容量为W的背包. 第i件物品的体积是w[i], 价值是v[i], 求将那些物品装入背包内可以使得价值总和最大.
"""


def max_weight_dp(w, weights: list[int], values: list[int]) -> int:
    n = len(weights)
    dp = [[0] * (w + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):  # 遍历每一个物品
        wi, vi = weights[i - 1], values[i - 1]
        for j in range(1, w + 1):
            if weights[i - 1] > j:  # 背包放不下物品i
                dp[i][j] = dp[i - 1][j]
            else:  # 放得下物品i
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)

    return dp[n][w]


def max_weight_opt(w, weights: list[int], values: list[int]) -> int:
    """
    注意: 在01背包中, 由于每个物品只能选择一次, 所以dp[i][j]依赖于dp[i-1][j], 也就是每次更新需要考虑此前未纳入该物品时候的状态.
    所以在使用滚动数组的时候就需要倒叙更新
    而在完全背包中, 则不同, 详细请看knapsack_g
    """

    dp = [0] * (w + 1)
    for idx, weight in enumerate(weights):  # 遍历每一个物品
        for j in range(w, weight - 1, -1):  # 从后向前遍历, 如果当前的物品的重量 > 背包的最大重量j 就停止遍历
            dp[j] = max(dp[j], dp[j - weight] + values[idx])  # 取较大值

    return dp[-1]


if __name__ == '__main__':
    w = 10
    weights = [2, 5, 3, 1, 8]  # 5 + 3 + 1 = 9      /  8 + 2 = 10       / 5 + 3 + 2 = 10  / 8 + 1 = 9
    values = [4, 5, 6, 5, 13]  # 5 + 6 + 5 = 16     / 13 + 4 = 17       / 5 + 6 + 4 + 16  / 13 + 5 = 18
    print(max_weight_dp(w, weights, values))
    print(max_weight_opt(w, weights, values))
